package tree.searchTree;

import figureAndGraph.Node;
import pojo.TreeNode;

/**
 * 功能描述: 获取满足最大搜索树的头结点
 * 2024/05/21
 * <p>
 * ZhangYi
 */
public class MaxSearchTreeHeadUtils {

    public static class Info{
        // 左树的最大值
        private int max;
        // 右树的最大值
        private int min;
        // 满足最大搜索树的头结点
        private TreeNode head;

        // 满足搜书树的节点树
        private int maxBSTSize;

        public Info(int max,
                    int min,
                    TreeNode head,
                    int maxBSTSize) {
            this.max = max;
            this.min = min;
            this.head = head;
            this.maxBSTSize = maxBSTSize;
        }
    }


    public static TreeNode getMaxSearchTreeHead(TreeNode root) {
        if (root == null){
            return null;
        }
        return getMaxSearchTreeHeadHelper(root).head;
    }

    /**
     * 功能描述:
     *
     * @param root 根
     * @return {@link Info }
     */
    private static Info getMaxSearchTreeHeadHelper(TreeNode root) {
        if (root == null){
            return null;
        }

        Info leftInfo= getMaxSearchTreeHeadHelper(root.left);
        Info rightInfo = getMaxSearchTreeHeadHelper(root.right);
        int max = root.getId();
        int min = root.getId();

        int maxBSTSize = 0;
        if (leftInfo != null){
            max = Math.max(leftInfo.max,max);
            min = Math.min(leftInfo.min,min);
            maxBSTSize = Math.max(leftInfo.maxBSTSize,maxBSTSize);
        }
        if (rightInfo!= null){
            max = Math.max(rightInfo.max,max);
            min = Math.min(rightInfo.min,min    );
            maxBSTSize = Math.max(rightInfo.maxBSTSize,maxBSTSize);
        }


        boolean isBST = leftInfo!= null && leftInfo.max < root.getId() ? true : false
                && rightInfo != null && rightInfo.min > root.getId()? true : false;

        TreeNode head = null;
        if (isBST){
            if (leftInfo != null){
                head = root;
                maxBSTSize = Math.max(leftInfo.maxBSTSize,maxBSTSize);
            }
            if (rightInfo != null){
                head = root;
                maxBSTSize = Math.max(rightInfo.maxBSTSize,maxBSTSize);
            }
        }


        return new Info(max,min,head,maxBSTSize);
    }


    public static void main(String[] args){
        TreeNode root = new TreeNode(2, "1");
        root.left = new TreeNode(1, "2");
        root.right = new TreeNode(3, "3");
        System.out.println(getMaxSearchTreeHead(root));

    }
}
